package com.boilermaker.springbootdemo;

import java.util.Scanner;

public class Teast1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入数组长度
        System.out.print("请输入数组的长度：");
        int n = scanner.nextInt();

        // 创建数组
        int[] array = new int[n];

        // 输入数组元素
        System.out.println("请输入" + n + "个元素（用空格或回车分隔）：");
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }

        System.out.println("输入 target");
        int target = scanner.nextInt();

        Solution solution = new Solution();
        solution.searchRange(array, target);
    }
}

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            int[] arr1 = { -1, -1 };
            return arr1;
        }
        int[] arr = {searchLeft(nums, target), searchRight(nums, target) };
        return arr;
    }

    public int searchLeft(int[] nums, int target) {
        int head = 0, tail = nums.length - 1;
        while (head < tail) {
            int mid = head + (tail - head) / 2;
            if (nums[mid] < target) {
                head = mid + 1;
            } else if (nums[mid] > target) {
                tail = mid - 1;
            } else {
                tail = mid;
            }
        }
        if (nums[head] == target && nums[tail] == target)
            return head;
        return -1;
    }

    public int searchRight(int[] nums, int target) {
        int head = 0, tail = nums.length - 1;
        while (head < tail) {
            int mid = head + (tail - head + 1) / 2;
            if (nums[mid] < target) {
                head = mid + 1;
            } else if (nums[mid] > target) {
                tail = mid - 1;
            } else {
                head = mid;
            }
        }
        if (nums[head] == target && nums[tail] == target)
            return head;
        return -1;
    }
}
